引言
图（网络）是一种表达对象之间复杂关系的通用数据结构，在计算机科学、社会科学、经济学、化学以及生物信息学等多个学科和领域中都大量存在。例如，网页之间的超链接关系构成了整个互联网；人们在脸书、微信以及微博等社交媒体上的好友或者关注关系构成了社会网络；学术论文之间的引用关系构成了引用网络；化学中不同的分子结构构成了大量结构不同的网络结构数据，等等。网络结构数据涉及广泛的应用。例如，在社交网络上预测两个用户是否会成为好友关系，在用户-商品网络上为用户推荐喜欢的商品，预测每个分子结构的化学属性等等。
这些应用的本质都是在图结构数据上进行的预测。对于预测任务，近年来以深度学习(deep learning)为代表的表征学习方法在语音识别、图像理解以及机器翻译等任务上取得了巨大的成功。这些方法通过设计多层的非线性神经网络从原始数据提取有效特征，整个模型建立在从数据的原始输入到目标任务的最终输出，实现了端到端的学习。由于深度学习等表征学习方法在多个领域的有效性，近年来涌现了大量的致力于面向网络结构数据的表征学习的工作。对于网络数据，传统的表示方法通常是邻接矩阵，并在此基础上设计机器学习算法。但是这种表示方法面临严重的高维以及数据稀疏性问题，不利于在网络结构上进行机器学习算法的计算。
网络表征学习
深度学习网络表征学习算法的目标是获得网络的低维稠密表示。对于大规模网络（如社会网络），网络表征学习的目标是把网络中的每个节点表示成为一个低维稠密的向量并且保证在这个低维空间上能够很好地保留网络的拓扑结构（见图1）。节点表示能够当作节点的特征用于节点分类、节点聚类、网络可视化、链接预测等不同的任务。受到词向量学习技术word2vec的启发，近年来产生了大量高效的网络节点表示算法，最经典的算法包括DeepWalk [1]、LINE [2]以及node2vec [3]等。这些算法本质上是通过保留网络的局部结构性来估计节点的表示。
图1 节点表示与全图表示对比示意图
由于学术界、工业界的广泛关注，网络节点表示已经取得了显著的进展，目前越来越多的研究开始转向整个网络（全图）的表示。与节点表示不同，整个网络表示的目标是将整个网络表示成一个低维向量，与其类似的还有保证具有相似结构的网络特征表示。这类方法具有大量的应用。例如，新药研发需要预测每个新研发出来的医药分子结构的性质，每个分子结构本质上也是一个图结构，通过学习分子结构的特征表示，有助于更有效地预测分子的性质。
由于不同网络的结构不同，学习整个网络的表示非常困难。传统的卷积神经网络(Convolutional Neural Network, CNN)主要适用于图像这类具有固定的二维网格结构的数据，递归神经网络(Recurrent Neural Network, RNN)主要适用于语音、自然语言处理序列数据。本文将系统地介绍如何拓展这些方法来学习任意网络结构的特征表示的一些最新工作。
全图表征学习的主要进展
已有的全图表征学习算法主要包括无监督和有监督两类，其中有监督算法又可以分为基于卷积网络和神经消息通信(neural message passing)两种算法。
基于深度核函数的无监督方法[4]
深度图核函数算法(deep graph kernels)建立在传统的图核函数方法的基础之上，每个图结构可以分解成为不同的子图结构（见图2）。但是，与传统的图核函数方法不同，对于深度核函数算法，每个子图结构表示为一个低维连续向量（见图3）。具体来说，每个图结构首先分解成为一系列子图结构，每个子图结构对应自然语言中的词，整个子图结构集合对应一个句子。通过分解不同的图结构，该算法建立了不同子图结构的共现关系，然后再利用词向量学习模型CBOW或者Skip-gram来学习子图结构向量。这类算法是无监督的，无须利用任何外部标签信息，只是利用了网络的内部结构。
图2 子图结构(substructures)[4]
图3 利用词向量模型学习子图结构的低维表示[4]
基于卷积神经网络的监督方法[5]
卷积神经网络在图像上取得了成功，其核心思想是构造不同的感受野(receptive fields)抽取图像的局部特征。为了把卷积神经网络运用于网络结构表征学习，关键问题是如何在网络结构上定义感受野。算法的第一步是在网络上选择一些重要的节点，把每个节点的局部结构作为感受野的输入。由于感受野必须是一个有序的特征序列，但是节点的局部网络拓扑结构是无序的，因此算法的第二步是把每个节点的局部结构变成一个有序的序列。把不同节点的局部结构变成一个有序特征序列之后，可以把标准的卷积网络算法运用到该特征序列上进行特征提取（见图4）。
图4 基于CNN的方法[5]
基于神经消息通信的监督方法[6]
神经消息通信算法通过不同节点之间的通信来对节点之间的局部结构特征进行建模。该算法基于传统的消息通信算法，但是与传统消息通信算法不同的是，不同的消息都是用向量表示的。从节点j到节点i的消息可以根据节点i的属性和节点i的其他邻居节点到节点i的信息共同来决定（图5第5行）。节点可以进行多次通信获得最终的消息表示。得到不同节点之间的消息表示之后，每个节点i的状态可以根据节点i的属性和节点i的所有邻居给它发送的消息来共同决定（图5第9行）。得到每个节点的状态表示之后，整个图的特征可以表示成为所有节点状态的总和。
图5 基于神经消息通信的方法[6]
应用任务
在很多领域都存在大量小的网络结构数据，因此全图表征学习有大量的应用。
1. 信息传播影响力预测
信息传播是社会网络和社会媒体分析中的一个重要研究内容，其中一个重要的任务是评估信息传播的影响力[7]。例如，在Twitter或者微博上预测一条微博的转发数量，在论文引用网络上预测一篇论文的引用数等。由于利用信息内容本身不足以准确地预测信息的影响力，在实际任务中可以根据信息早期的传播网络结构特征来预测最终的影响力。深度学习技术可以有效地提取和结合节点内容特征和网络结构特征来进行特征学习。
2. 新药发现
新药发现的一个重要步骤是检测新发现的分子结构的化学与医药特性。传统的做法是通过大量的化学与临床实验来验证，整个实验周期非常长、代价高。机器学习特别是深度学习技术给新药发现领域带来了巨大的机会。每个分子结构本质上是一个图结构。全图表征学习技术可以通过学习大量的分子结构样本来准确和高效地提取分子结构的特征，准确地预测分子结构的化学属性。这将极大地降低新药发现的成本，缩短新药发现的周期。
3. 社区推荐或者分类
社区研究是社会网络分析中的一个重要课题。每个社区本质上是网络的一个子图。学习社区的特征表示可以为很多社区相关的应用服务。例如，通过学习用户和整个社区的特征向量，我们可以计算用户和不同社区的相关性，从而为用户推荐其感兴趣的社区；通过学习整个社区的特征表达，我们可以预测社区的类别、增长速度等特性。
总结与展望
综上所述，网络表征学习近年来在社会网络分析、新药发现、个性化推荐等不同领域都取得了重要的进展。目前大部分的研究工作主要集中在研究大规模网络的节点表示上，越来越关注整个网络的表征学习，相关的应用有信息传播影响力预测、社区推荐、社区分类、新药发现等领域。但是，关于整个网络表征学习的研究才刚刚开始，还面临很多挑战：
1. 对图中远距离节点之间的相关性进行建模。现在已有的算法（如基于卷积神经网络以及神经消息通信的算法）主要还是对局部节点之间的相关性建模，很难捕捉长距离节点之间的相关性。
2. 小数据学习。现在深度学习的主要应用领域如图像、语音、自然语言理解等都包含大量的标注数据，这也是深度学习能够在这些领域取得成功的重要原因之一。但是对于新药发现等领域，标注数据还相对较少。因此，如何利用小数据以及大量无标注数据进行学习将会成为一个重点和难点。
3. 大规模训练。已有的大部分深度学习框架如Tensorflow、Theano以及PyTorch一般都假定输入的数据具有固定的结构（如图像、自然语言处理），但是对于全图表示而言，不同输入数据的结构完全不一样，给模型训练带来了巨大的挑战。在将来，如何大规模训练全图表征学习算法将成为一个重要的瓶颈。
参考文献
[1] Perozzi B, Al-Rfou R, Skiena S. DeepWalk: online learning of social representations[C]// Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM Press, 2014:701-710.
[2] Tang J, Qu M, Wang M, et al. LINE: Large-scale Information Network Embedding[C]// Proceedings of the 24th International Conference on World Wide Web. 2015, 2:1067-1077.
[3] Grover A, Leskovec J. node2vec: Scalable feature learning for networks[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM Press, 2016: 855-864.
[4] Yanardag P, Vishwanathan S. Deep Graph Kenerls[C]//Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM Press, 2015: 1365-1374.
[5] Niepert N, Ahmed M, Kutzkov K. Learning Convolutional Neural Networks for Graphs[C]//Proceedings of the 33rd International Conference on International Conference on Machine Learning. JMLR Press.2016: 2014-2023.
[6] Dai H, Dai B, Song L. Discriminative Embeddings of Latent Variable Models for Structured Data[C]// Proceedings of the 33rd International Conference on International Conference on Machine Learning. JMLR Press.2016: 2702-2711.
[7] Li C, Ma J, Guo X, et al. DeepCas: an End-to-end Prediction of Information Cascades[C]// Proceedings of the 26th International Conference on World Wide Web.2017: 577-586.
所有评论仅代表网友意见